This invention relates to a lossy data compression system using vector quantisation, for reducing data volumes generated by hyper-spectral imaging devices.
The next generation of satellite-based remote sensing instruments will produce an unprecedented volume of data. Imaging spectrometers, also known as hyper-spectral imaging devices, are prime examples. They collect image data in hundreds of spectral bands simultaneously from the near ultraviolet through the short wave infrared, and are capable of providing direct identification of surface materials.
Hyper-spectral data thus collected are typically in the form of three-dimensional (3D) data cube. Each data cube has two dimensions in the spatial domain defining a rectangular plane of image pixels, and a third dimension in the spectral domain defining radiance levels of multiple spectral bands per each image pixel. The volume and complexity of hyper-spectral data present a significant challenge to conventional transmission and image analysis methods. The raw data rates for transmitting such data cubes can easily exceed the available downlink capacity or on-board storage capacity of existing satellite systems. Often, therefore, a portion of the data collected on board is discarded before transmission, by reducing the duty cycle, reducing the spatial or spectral resolution, and/or reducing the spatial or spectral range. Obviously, in such cases large amounts of information are lost.
For data processing, a similar problem occurs. In computing, a current trend is toward desktop computers and Internet based communications. Unfortunately, the data cubes require a tremendous amount of storage and, for processing, the storage is preferably random access memory (RAM). Current desktop computers often lack sufficient resources for data processing of data cubes comprising spectral data.
Recent work related to data compression of multi-spectral and hyper-spectral imagery has been reported in the literature, but most of these studies relate to multi-spectral imagery comprised of only a few spectral bands. These prior art systems for multi-spectral imagery yield small compression ratios, usually smaller than 30:1. There are two reasons for this:
1) the prior art systems do not efficiently remove the correlation in the spectral domain, and
2) the redundancy of multi-spectral imagery in the spectral domain is relatively small compared to that of hyper-spectral imagery.
Gen et al teach two systems for hyper-spectral imagery. The first system uses trellis coded quantisation to encode transform coefficients resulting from the application of an 8xc3x978xc3x978 discrete cosine transform. The second system uses differential pulse code modulation to spectrally decorrelate data, while using a 2D discrete cosine transform for spatial decorrelation. These two systems are known to achieve compression ratios of greater than 70:1 in some instance; however, it is desirable to have higher compression ratios with simpler coding structures than those reported in the literature.
In an article entitled xe2x80x9cLossy Compression of Hyperspectral Data Using Vector Quantizationxe2x80x9d by Michael Ryan and John Arnold in the journal Remote Sens. Environ., Elsevier Science Inc., New York, N.Y., 1997, Vol. 61, pp. 419-436, an overview of general vector quantization techniques as are now known is presented. The article is herein incorporated by reference. In particular, the authors describe issues such as distortion measures and classification issues arising from lossy compression of hyper-spectral data using vector quantization.
Data compression using Vector Quantisation (VQ) has received much attention because of its promise of high compression ratio and relatively simple structure. Unlike scalar quantisation, VQ requires segmentation of the source data into vectors. Commonly, in two-dimensional (2D) image data compression, a block with nxc3x97m (n may be equal to m) pixels is taken as a vector, whose length is equal to nxc3x97m. Vectors constituted in this way have no physical analogue. Because the blocks are segmented according to row and column indices of an image, the vectors obtained in this manner change at random as the pixel patterns change from block to block. The reconstructed image shows an explicit blocking effect for large compression ratios.
There are several conventional approaches to constituting vectors in a 3D data cube of hyper-spectral imagery. The simplest approach is to treat the 3D data cube as a set of 2D monochromatic images, and segment each monochromatic image into vectors independently as in the 2D-image case. This approach, however, suffers from not taking advantage of the high correlation of data in the spectral domain. There is therefore a need for a data compression system that takes advantage of correlation in the spectral domain and the 2D spatial correlation between adjacent image pixels.
The VQ procedure is known to have two main steps: codebook generation and codevector matching. VQ can be viewed as mapping a large set of vectors into a small subset of indexed codevectors forming a codebook. During encoding, a search through a codebook is performed to find a best codevector to express each input vector. The index or address of the selected codevector in the codebook is stored associated with the input vector or the input vector location. Given two systems having a same codebook, transmission of the index to a decoder over a communication channel from the first system to the second other system allows a decoder within the second other system to retrieve the same codevector from an identical codebook. This is a reconstructed approximation of the corresponding input vector. Compression is thus obtained by transmitting the index of the codevector rather the codevector itself. Many existing algorithms for codebook designs are available, such as the LBG algorithm reported by Linde, Buzo and Gray, the tree-structure codebook algorithm reported by Gray, the self organising feature map reported by Nasrabadi and Feng. Among these, the LBG algorithm is most widely used because of its fidelity. The disadvantages of the LGB algorithm are its complexity and the time burden taken to form the codebook. When the input data is a 3D data cube of hyper-spectral imagery, the processing time can be hundreds of times higher than the normal 2D-image case. There is therefore a need for faster codebook generation algorithms with relatively high fidelity.
It would also be advantageous to provide a method of data compression wherein data compressed according to the method is useful for some forms of data processing, image generation, and data viewing.
It is an object of the present invention to provide a data compression system that allows viewing and analysis of large datastructures without decompression of the entire datastructure. It is yet another object of the invention to provide a data compression algorithm that would allow relatively fast processing of 3D data cubes in a compressed form.
In accordance with the invention there is provided a method of processing hyper-spectral image data defining signal levels of multiple spectral bands in encoded form, the encoded form comprising an array of indices and a codebook comprising a plurality of vectors, the method comprising the steps of:
for each image pixel,
determining a first band from the multiple spectral bands and an index from the array of indices, the index indicative of a vector within the codebook, and
retrieving from the indicated vector within the codebook a value corresponding to the first band; and,
displaying an image comprising image pixels, image pixel values based upon the values retrieved for each image pixel.
In accordance with the invention there is also provided a method of processing hyper-spectral image data defining signal levels of multiple spectral bands per image pixel in encoded form, the encoded form comprising an array of indices and a codebook, the method comprising the step of:
processing spectral vectors within the codebook to produce a processed codebook, each spectral vector processed in isolation.
According to an embodiment the method comprises the further steps of:
transmitting the codebook and the array of indices from a first computer to a second other computer, the second other computer remote from the first computer,
wherein the step of processing is performed on the second other computer and includes determining from the codebook and the array of indices, data within the hyper-spectral data that is significant for further analysis;
requesting the data from the first computer;
compressing uncompressed hyper-spectral data associated with the requested data according to a known compression algorithm to produce compressed data; and,
transmitting the compressed data to the second computer.
In accordance with the invention there is also provided a method of processing hyper-spectral image data defining signal levels of multiple spectral bands per image pixel in encoded form, the encoded form comprising an array of indices and a codebook, the method comprising the step of:
processing spectral vectors within the codebook and data from the index map to extract information from the codebook and index map other than pixel values for display.
In accordance with another aspect of the invention there is provided a system for processing hyper-spectral image data defining signal levels of multiple spectral bands in encoded form, the encoded form comprising an array of indices and a codebook comprising a plurality of vectors, the system comprising:
means for selecting for each image pixel a first band from the multiple spectral bands and an index from the array of indices, the index indicative of a vector within the codebook, and
means for retrieving for each image pixel from the indicated vector within the codebook a value corresponding to the first band; and,
means for displaying an image comprising image pixels, image pixel values based upon the values retrieved for each image pixel.
In accordance with the other aspect of the invention there is also provided a system for processing hyper-spectral image data defining signal levels of multiple spectral bands per image pixel in encoded form, the encoded form comprising an array of indices and a codebook, the system comprising:
means for processing each spectral vector within the codebook in isolation to produce a processed codebook.
In accordance with yet another aspect of the present invention there is provided a system for processing in a compressed form, hyper-spectral image data defining radiance levels of multiple spectral bands per image pixel, said system being initially trained with image data defining a predetermined set of training image pixels, said system comprising:
a) vector constitution means having an input for receiving and representing the image data as an array of spectrum image vectors {right arrow over (x)}p, said array having a predetermined dimension n, each said vector to characterise the spectral bands of an image pixel p, said vector having a predetermined dimension of Nb components xp(xcex), xcex having any value between 1 and Nb;
b) spectral compressor responsive to the vector constitution means, including a compression algorithm for reducing any of said spectrum image vectors to a binary image vector {right arrow over (X)}p having a predetermined length L;
c) a codevector generator responsive to the spectral compression means, for receiving a predetermined set of training binary image vectors corresponding to the predetermined set of training image pixels, said generator having a codevector algorithm for deriving from said set of training binary image vectors a finite set of binary codevectors {right arrow over (Y)}q and having means for storing said set of codevectors;
d) vector matching means responsive to the spectral compressor for receiving the binary image vectors and responsive to the codevector generator for reading the binary codevectors, said matching means including a distance algorithm for calculating the distance Dpq of any received binary imagevector {right arrow over (X)}p to each element {right arrow over (Y)}q in the finite set of binary codevectors, and for selecting a matched binary codevector having shortest distance from said received binary image vector, as a compressed form of the spectrum image vector {right arrow over (x)}p, said matching means having an output for providing an array of said matched binary codevectors as a compressed form of the hyper-spectral image data suitable for further image processing;
In an embodiment of the present invention, the compression algorithm used in spectral compression, upon receiving a spectral image vector {right arrow over (x)}p performs the steps of:
a) calculating a spectral algebraic mean xcexcp of the Nb components xp(xcex) of the received spectrum image vector {right arrow over (x)}p;
b) generating an amplitude binary vector {right arrow over (X)}pa having a length of Nb bits Xpa(xcex), xcex having any value between 1 and Nb, where Xpa(xcex) equals a first binary level when xp(xcex) is greater than or equal to xcexcp, and Xpa(xcex) equals a second binary level when xp(xcex) is smaller than xcexcp;
c) generating a slope binary vector {right arrow over (X)}ps having a length of Nbxe2x88x922 bits Xps(xcex), xcex having a value between 2 and Nbxe2x88x921, where Xps(xcex) equals a first binary level when xp(xcex+1) is greater than or equal to xp(xcexxe2x88x921), and Xps(xcex) equals a second binary level when xp(xcex+1) is smaller than xp(xcexxe2x88x921);
d) calculating a spectral mean deviation MDi as the mean of the absolute difference between each of the Nb components xp(xcex) of the spectrum image vectors {right arrow over (x)}p and the spectral algebraic mean xcexcp;
e) generating a mean deviation binary vector {right arrow over (X)}pMD having a length of Nb bits XpMD(xcex), xcex having any value between 1 and Nb, where XpMD(xcex) equals a first binary level when the absolute difference between xp(xcex) and xcexcp is greater than or equal to MDp, and XpMD(xcex) equals a second binary level when the absolute difference between xp(xcex) and xcexcp is smaller than MDp; and
f) reducing the received spectrum image vectors to a binary image vector {right arrow over (X)}p having a length L=3Nbxe2x88x922 bits, in the form of a concatenation of the amplitude binary vector {right arrow over (X)}pa, the slope binary vector {right arrow over (X)}ps and the mean deviation binary vector {right arrow over (X)}pMD.
In another embodiment of the present invention, the distance algorithm for determining a distance such as a Hamming distance, Dpq, is capable of calculating the distance between a binary vector {right arrow over (X)}p and a binary codevector {right arrow over (Y)}q as the arithmetic sum of bit-wise exclusive-OR operations on all bit pairs (Xp(l), Yq(l)) corresponding to {right arrow over (X)}p and {right arrow over (Y)}q, l having any value between 1 and L; alternatively, a Euclidean distance is calculated between the image vectors {right arrow over (x)}p and codevectors {right arrow over (y)}q.
In accordance with the present invention there is also provided a system for compressing hyper-spectral image data defining radiance levels of multiple spectral bands per each pixel of a two-dimensional image having Nr rows and Nc columns of pixels, said system comprising:
a) vector constitution means for receiving and representing the image data as a two-dimensional vector array of Nrxc3x97Nc spectrum image vectors {right arrow over (x)}p, p having any value from 1 to Nrxc3x97Nc each said vector being positioned at a row co-ordinate i and a column co-ordinate j of said vector array, to characterise the spectral bands of an image pixel at similar i and j co-ordinates within the two-dimensional image, i having any value from 1 to Nr and j having any value from 1 to Nc, said vector having a predetermined dimension of Nb components xp(xcex), xcex having any value between 1 and Nb;
b) spectral compressor responsive to the vector constitution means for reducing any of said spectrum image vectors to a binary image vector {right arrow over (X)}p;
c) a codevector generator responsive to the spectral compressor for receiving a predetermined set of training binary image vectors, deriving therefrom a finite set of binary codevectors {right arrow over (Y)}q, each codevector identifiable with an index;
d) a codebook responsive to the codevector generator for storing, in the form of a look-up table, said set of binary codevectors and the set of indices in a one-to-one mapping relationship between each binary codevector and its corresponding index;
e) vector matching means responsive to the spectral compressor and the codebook, for receiving the binary image vectors, said matching means including a distance algorithm for calculating the distance Dpq of any received binary image vector {right arrow over (X)}p to each element {right arrow over (Y)}q in the set of binary codevectors in the codebook, and for selecting a matched binary codevector having shortest distance from said received binary image vector;
f) a correlation encoder responsive to the vector matching means and the codebook for receiving said matched binary codevectors, said encoder comprising
i) means for retrieving from the codebook an index corresponding to each matched binary codevector received therein,
ii) means for forming a two-dimensional index array of Nrxc3x97Nc indices Cp, each said index being positioned at a row co-ordinate i and a column co-ordinate j of said index array, to correspond to an image pixel at similar i and j co-ordinates within the two-dimensional image,
iii) a movable two-dimensional window having Wr rows and Wc columns, Wr and Wc having predetermined values of less than or equal to Nr and Nc respectively, said window being capable of reading the indices in adjacent index positions within any cell of Wrxc3x97Wc indices from the index array,
iv) a correlation algorithm for moving the window in a predetermined sequence across the entire index array, having the window read the indices of one cell at a time, and generating a correlation symbol for each cell read by the window, each said symbol to refer to no more than once to an index value read within said cell, and to define a dissimilarity pattern among index values within said cell.
This embodiment is intended to reduce the correlation in both spatial and spectral domain with the additional benefit of reduced computation complexity.
In accordance yet with another aspect of the present invention there is provided a system for compressing, and communicating in a compressed form, hyper-spectral image data defining radiance levels of multiple spectral bands per image pixel, said system being initially trained with image data defining a predetermined set of training image pixels, said system comprising:
a) vector constitution means for receiving and representing the image data as an array of spectrum image vectors {right arrow over (x)}p, said array having a dimension n, each said vector to characterise the spectral bands of an image pixel p, said vector having a predetermined dimension of Nb components xp(xcex), xcex having any value between 1 and Nb;
b) spectral compressor responsive to the vector constitution means, including a compression algorithm for reducing any of said spectrum image vectors to a binary image vector {right arrow over (X)}p;
c) a codevector generator responsive to the spectral compressor and the vector constitution means, for receiving a predetermined set of training spectrum image vectors and a corresponding set of binary image vectors thereto, said generator having a codevector algorithm for deriving from said set of spectrum image vectors a finite set of spectrum codevectors {right arrow over (y)}q, and for deriving from the corresponding binary image vectors a finite set of binary codevectors {right arrow over (Y)}q, and generating a set of indices Cq corresponding to said spectrum codevectors;
d) a codebook responsive to the codevector generator for storing, in the form of a look-up table, said finite set of spectrum codevectors {right arrow over (y)}q, together with said finite set of binary codevectors {right arrow over (Y)}q in a one-to-one mapping relationship to said corresponding indices Cq;
e) vector matching means responsive to the spectral compressor for receiving the binary image vectors, and responsive to the codebook for reading the set of binary codevectors, said matching means including a distance algorithm for calculating the distance Dpq of any received binary image vector {right arrow over (X)}p to each read codevector {right arrow over (Y)}q, and for selecting a matched binary codevector having shortest distance from said received binary image vector;
f) an encoder responsive to the vector matching means and the codebook for receiving said matched binary codevectors, said encoder comprising means for retrieving from the codebook an index to correspond to each matched binary codevector received by the encoder, and for forming an array of indices to render a compressed form of the hyper-spectral image data, suitable for delivery to a communications or storage medium;
g) a decoder responsive to the communications medium for receiving said indices, referring to the codebook to map each received index into a corresponding spectrum codevector, and forming an array of reconstructed spectrum codevectors suitable for image display or further image processing.
Unlike conventional compression and coding schemes, the vectors constituted by the present invention have a physical meaning: each vector is a spectral vector representative of a spectrum, and each spectrum is an indicator of the material in a surface such as the earth""s surface that lies within the field of view. Since the number of materials in an imaged scene is usually limited, the number of different encoded spectra can be much smaller than the total number of vectors Nrxc3x97Nc. By taking advantage of this redundancy, the present invention expresses all the spectral vectors using a codebook with comparatively few binary codevectors and achieves good reconstruction fidelity. This way, the invention makes better use of the high correlation often found between bands in the spectral domain and can achieve a relatively high compression ratio. Furthermore, encoding the image vectors in a binary form permits faster codebook generation and faster codevector matching. In view of the physical meaning attached to each encoded binary vector, it would be possible to apply image-processing operations to the compressed form of the much shorter and fewer binary vectors than the hyper-spectral image data in its raw uncompressed form.